The SRT (Sweeney, Robertson, Tocher) algorithm has been employed for some time in digital division to divide a divisor into a dividend to produce a quotient. The basic SRT type algorithm will be reviewed along with a particular prior art method to select a quotient using a Partial Remainder-Divisor (P-D) plot. My inventive method of transforming, or pre-adjusting, the divisor and dividend may, however, be used in a number of other division methods which will become apparent to those skilled in the art.
The general SRT algorithm uses nonrestoring floating point division where the quotient may be positive or negative and is selected from the signed digit set EQU {-m, . . . , -1, 0, 1, . . . , m} (1)
where ##EQU1## r being the radix used in the division.
Digital division consists of the basic operations of normalization, a recursive process, and a terminal operation, e.g., changing the form of the remainder. Since the recursive process is repetitive, time saved on each recursive step results in a substantial time savings in the overall division process.
Normalization, using the IEEE standard for floating point division, requires the divisor and dividend to be in the range EQU 1.ltoreq.DR&lt;2, and (3) EQU 1.ltoreq.DD&lt;2, (4)
where DR is the divisor and DD is the dividend. These ranges are easily obtained by shifting the binary divisor and dividend until the first nonzero digit (i.e., 1) is to the left of the radix point.
The recursive relationship is defined by EQU P.sub.j+1 =rp.sub.j -q.sub.j+1 DR, (5)
where
j=the recursive index=0, 1, . . . , n-1 PA1 p.sub.j =the partial remainder used in the jth cycle PA1 p.sub.o =the dividend DD PA1 p.sub.n =the remainder PA1 q.sub.j =the jth quotient digit in a resulting quotient of the form PA1 n=the number of digits in the quotient PA1 DR=the divisor, and PA1 r=the radix. PA1 j=0 (initially) PA1 p.sub.o =DD=5 PA1 DR=7 PA1 rp.sub.o =50 PA1 q.sub.j+1 DR=7.times.7=49 PA1 p.sub.j+1 =1, and PA1 r=10 ##EQU2## As seen, the partial remainder p.sub.j+1 is obtained by multiplying q.sub.j+1 by the divisor DR and subtracting this product from the shifted partial remainder rp.sub.j.
q.sub.0 .multidot.q.sub.1 q.sub.2 . . . q.sub.n
This recursive relationship is amply discussed in the report, "The Theory and Implementation of SRT Division", by D. Atkins, Report No. 230, Dept. of Computer Sci., University of Ill., Urbana, Illinois, June 1, 1967, incorporated herein by reference, and in the article, "Higher-Radix Division Using Estimates of the Divisor and Partial Remainders", by D. Atkins, IEEE Trans. on Computers, Vol. C-17, No. 10, Oct. 68, incorporated herein by reference.
A simple example of division using the recursive method of equation 5 is shown below as equation 6, where 7 is the divisor and 5 is the dividend, and where
One of the advantages of using nonrestoring division is that the quotient digits can comprise positive and negative digits, allowing a quotient to be expressed in more than one way, or redundantly. For example in radix 4 division, where the range of q.sub.j+1 is chosen to be {-2, -1, 0, 1, 2}, the decimal number six may be expressed with two quotient digits as follows, where X represents the negative of X: EQU q.sub.1 q.sub.2 .fwdarw.2 2=8-2, or (7) EQU q.sub.1 q.sub.2 .fwdarw.1 2=4+2. (8)
This redundancy permits a range of q.sub.j+1 instead of a precise q.sub.j+1, since the error of q.sub.j+1 can be compensated for in q.sub.j+2. Hence, with redundancy, the comparison of divisor DR and shifted partial remainder rp.sub.j need not be precise to select a valid q.sub.j+1, and no time is spent having to restore a partial remainder p.sub.j+1 to a positive value when a selected quotient digit q.sub.j+1 is too large, as required in a restoring type division method.
The required number of bits, or precision, of the divisor and shifted partial remainder necessary to generate a valid q.sub.j+1 will now be determined. In manual division, without redundant quotient digits, p.sub.j+1 is made to be in the range EQU 0.ltoreq.p.sub.j+1 .ltoreq.DR; (9)
otherwise, a new p.sub.j+1 must be selected. With redundant quotient digits, however, a negative p.sub.j+1 is allowed, and thus, the range restriction is EQU .vertline.p.sub.j+1 .vertline..ltoreq.K.vertline.DR.vertline., (10)
where K is the normalized amount of redundancy. Since the range of .vertline.p.sub.j+1 .vertline. is related to the amount of redundancy in the quotient, and the amount of redundancy in the quotient is related to the digit set of equations 1 and 2, then .vertline.p.sub.j+1 .vertline. is related to m, where 2m+1 is the number of possible digits in each quotient digit q.sub.j+1 and m is in the range ##EQU3## Since maximum redundancy is achieved with a maximum m of r-1, the maximum range of .vertline.p.sub.j+1 .vertline. is EQU .vertline.p.sub.j+1 .vertline..ltoreq..vertline.DR.vertline.(12)
Hence, for maximum redundancy, ##EQU4## For minimum redundancy, ##EQU5## and hence, ##EQU6##
To illustrate the redundancy of q.sub.j+1 in a division process, equation 5, shown again below, EQU p.sub.j+1 =rp.sub.j -q.sub.j+1 DR (5)
is plotted as p.sub.j+1 vs. rp.sub.j in FIG. 1. The value rp.sub.j is expressed along the x-axis in terms of the divisor DR. The upper and lower bounds of p.sub.j+1 are shown as +DR and -DR, respectively; this assumes that K equals unity in accordance with equation 12 and, thus, EQU m=r-1, (15)
meaning that there is maximum redundancy, or overlap, in the quotient. The diagonal "q-lines" have a slope r, where r is the radix. The left and right boundaries are determined by the number of quotient digits, m, where in FIG. 1 the right boundary has an upper vertex being the intersection of q-line q.sub.j+1 =m and p.sub.j+1 =+DR, and the left boundary has a lower vertex being the intersection of q-line q.sub.j+1 =m and p.sub.j+1 =-DR.
As seen, redundancy is illustrated in FIG. 1 by the example where an rp.sub.j of approximately 2.5DR can have a corresponding q.sub.j+1 of either 2 or 3. Depending on whether q.sub.j+1 is chosen to be 2 or 3, p.sub.j+1 will result in either a positive remainder or a negative remainder. Since a certain range exists for rp.sub.j where q.sub.j+1 can either be a 2 or 3, only the first few significant bits of the shifted partial remainder rp.sub.j need to be examined in order to select a valid q.sub.j+1. The selected value of q.sub.j+1 is then multiplied by the actual precise divisor DR and subtracted from the actual precise rp.sub.j, as dictated by the recursive relationship of equation 5, to determine p.sub.j+1. P.sub.j+1 is then shifted to become rp.sub.j, and the first few significant bits of rp.sub.j are then used to select the next q.sub.j+1 and corresponding p.sub.j+1. Hence, the amount of redundancy determines how many bits of rp.sub.j and DR must be taken into account to select a valid q.sub.j+1.
As seen, redundancy is determined by the number of possible digits for each q.sub.j+1 value (i.e., 2m+1), where, given a radix r, ##EQU7## The optimal choices of m, and thus K, of equation 10 depend on design trade-offs. For example, choosing a large m value (e.g., m=r-1) necessitates added hardware complexity but increases the redundancy, or K value, of the quotient. The increased redundancy results in the ability to inspect fewer bits of the shifted partial remainder rp.sub.j and divisor DR when selecting a quotient digit q.sub.j+1. Added background material regarding high-radix division may be found in the book, "Computer Arithmetic", by K. Hwang, John Wiley & Sons (1979), pp. 213-239, incorporated herein by reference, and the aforementioned report and article by D. Atkins.
Another graphical representation of the relationship between DR, rp.sub.j, and q.sub.j+1 is illustrated in a partial remainder vs. divisor (P-D) plot, shown in FIG. 2. FIG. 2 shows a P-D plot for r=4 and m=2, where the q.sub.j+1 digits are selected from the group {-2, -1, 0, 1, 2}. As in the p.sub.j+1 vs. rp.sub.j plot of FIG. 1, the P-D plot of FIG. 2 is based on the recursive relationship of equation 5.
As seen from FIG. 2, the intersection of divisor DR and shifted partial remainder rp.sub.j (in this case 4p.sub.j) may fall within overlapping q.sub.j+1 values, where either q.sub.j+1 value is valid. The selected q.sub.j+1 value is then multiplied by the full divisor DR and subtracted from the full shifted partial remainder rp.sub.j to determine p.sub.j+1. The plot is symmetric about both the x and y axes.
The plot is derived from the following general parameters. For a fixed quotient digit q.sub.j+1, the upper limit of rp.sub.j as a function of the divisor DR occurs when p.sub.j+1 is a maximum, as seen by equation 5. Partial remainder p.sub.j+1 is, therefore, a maximum when ##EQU8## where m/r-1 is equal to the measure of redundancy, K. Hence, from equation 5, rp.sub.j is a maximum when ##EQU9## Partial remainder p.sub.j+1 is a minimum when ##EQU10## Hence, ##EQU11##
By plotting the linear equations of equations 17 and 19 for a fixed q.sub.j+1 as functions of DR, with q.sub.j+1 ranging from -m to m in steps of 1, a P-D plot, such as shown in FIG. 2, is developed for a given m and r. The shifted partial remainder rp.sub.j value in terms of the divisor DR is given for each q-line of the P-D plot on the right side of FIG. 2 and is equivalent to the slope of the q-line.
In accordance with the P-D plot of FIG. 2, a given value of the divisor DR and shifted partial remainder rp.sub.j, where radix r=4, will specify a point in an area between rp.sub.jmax and rp.sub.jmin denoted as a q(i) area, where q.sub.j+1 =i. The selected q.sub.j+1 is then used in forming the next partial remainder p.sub.j+1. The redundancy of q.sub.j+1 is demonstrated by the overlapping of consecutive q(i) areas where either i or i-b 1 is a valid choice for q.sub.j+1. This overlapping of q(i) areas allows the divisor DR and shifted partial remainder rp.sub.j to be only within a certain range for the selection of a valid q.sub.j+1. Steps have been drawn with dashed lines within the overlapping q(i) areas in FIG. 2 which illustrate various arbitrary divisor DR intervals within boundaries defined by the first four significant bits of divisor DR. The steps illustrate that only the first four bits of the divisor DR need to be inspected to determine the DR interval, which in turn provides the necessary precision to select a valid q.sub.j+1. These steps may be modified to represent any interval of the divisor DR where a single interval of DR is defined within selected boundaries and where any DR within that interval results in the selection of a valid q.sub.j+1 given a sufficiently precise rp.sub.j value.
The vertical distance between two steps in consecutive overlapping q(i) areas defines the maximum range of the shifted partial remainder rp.sub.j for the permissible divisor DR interval. In FIG. 2, the steps are drawn so that the ranges of rp.sub.j are defined within boundaries defined by the first four significant bits of the shifted partial remainder rp.sub.j. Thus, imaginary rectangles are formed between the steps within consecutive overlapping q(i) areas representing a range of divisors DR and shifted partial remainders rp.sub.j which are associated with a particular q.sub.j+1.
In a division operation, the maximum and minimum values within a selected range of the shifted partial remainder rp.sub.j and divisor DR in a P-D plot are compared with a sufficient number of high order bits of the actual shifted partial remainder rp.sub.j and divisor DR to determine which of the ranges rp.sub.j and DR fall into, and a q.sub.j+1 is selected.
As seen by inspection of FIG. 2, the intervals of the divisor DR can be increased in range as the divisor DR increases from a value of 1.0 to 2.0.
One way to implement a divider is to design hardware and software to logically duplicate the P-D plot method of selecting a q.sub.j+1. This class of divider is referred to a table look-up model.
Some division techniques which do not use a table look-up model transform the divisor to enable a more efficient selection of q.sub.j+1. One such algorithm has been proposed by Milos Ercegovac et al. in a paper entitled "A Division Algorithm with Prediction of Quotient Digits", Proc. 7th IEEE Symposium on Computer Arithmetic, June 1985, pp. 51-56. In the Ercegovac method, the quotient digits are directly determined based on an estimate, or rounding, of the partial remainder. For the rounded partial remainder to directly determine the proper quotient digit, the divisor DR is transformed to be in the range EQU 1-.alpha..ltoreq.DR.ltoreq.1+.alpha., (20)
where .alpha. is a constant between zero and one and is defined by the equation, ##EQU12## and where p is the highest digit in the quotient digit set (i.e., -p.ltoreq.q.ltoreq.p),
k is the fractional digit position after which the partial remainder is truncated, and PA0 r is the radix.
The dividend then has to be adjusted commensurate with the transformation of the divisor so as not to affect the quotient. As is apparent, the implementation of the algorithm to transform the divisor is fairly complex and cannot be practically implemented in an integrated circuit.
In an SRT divider, the cycle time (i.e., time to complete each iteration) is dominated by the time it takes to generate each q.sub.j+1 by inspecting the most significant bits (msb's) of the shifted partial remainder rp.sub.j and divisor DR. The logic required to determine q.sub.j+1 from these msb's is called the quotient select logic. For higher radix dividers (e.g., r&gt;2), large amounts of logic are required for quotient selection, and, for larger designs, ROM's are involved. Consequently, with more quotient select logic, the divider speed is reduced.
The prior art has proposed various methods to scale the divisor and dividend to reduce the size of the quotient logic. Milos Ercegovac has proposed one method, as stated previously, where the divisor is transformed into a range between 1+.alpha. and 1-.alpha., where .alpha. is a constant between zero and one. J. Robertson, in a paper entitled, "Normalization and Quotient Digit Selection for a Variable Precision Arithmetic Unit", University of Illinois, Report No. UIUCDCS-R-86-1229, April 1986, set out to simplify the quotient select hardware by normalizing the divisor. Mr. Robertson's paper is primarily concerned with how to get radix four numbers into a normalized fractional format.
Up until now no easily implemented method of increasing the efficiency and speed of a divider, such as one incorporating a look-up table model, has been publicly proposed.